Fenwick Tree

定义 Definition

Fenwick tree（也常叫 Binary Indexed Tree, BIT）是一种用于高效维护数组“前缀和/累计频率”的数据结构，支持在 O(log n) 时间内进行单点更新与前缀查询（以及由此扩展的区间查询）。

发音 Pronunciation (IPA)

/ˈfɛn.wɪk triː/

例句 Examples

Use a Fenwick tree to query prefix sums quickly.
使用 Fenwick 树可以快速查询前缀和。

In competitive programming, a Fenwick tree is often used to handle dynamic frequency counts with many updates and queries.
在算法竞赛中，Fenwick 树常用于处理需要频繁更新与查询的动态频率统计。

词源 Etymology

“Fenwick tree”得名于计算机科学家 Peter M. Fenwick，他在 1994 年发表论文介绍了这种用于“累计频率表（cumulative frequency tables）”的高效结构；由于其实现常用“二进制低位”来跳转索引，因此也被称为 Binary Indexed Tree（二进制索引树）。

相关词 Related Words

• Binary Indexed Tree
• Segment Tree
• Prefix Sum
• Range Query
• Cumulative Frequency
• Data Structure
• Update
• Query

文学与作品中的用例 Literary Works

• Peter M. Fenwick, “A New Data Structure for Cumulative Frequency Tables”（1994）：提出并系统描述该结构的经典论文。
• Steven Halim & Felix Halim, Competitive Programming（多版）：常以 Fenwick tree/BIT 作为前缀和与频率查询的核心数据结构讲解。
• CP-Algorithms（在线算法手册）相关条目：以“Fenwick Tree / Binary Indexed Tree”为题，广泛用于竞赛与工程实践的参考资料。